#include <stdio.h>
#include <stdlib.h>
#include "rbtree.h"

#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color == RED)
#define rb_is_black(r) ((r)->color == BLACK)
#define rb_set_black(r) do {(r)->color = BLACK;} while(0)


rbroot * create_rbtree()
{
    rbroot * root = (rbroot * ) malloc(sizeof(rbroot));
    root->node = NULL;

    return root;
}

static void preorder(rbtree tree)
{
    if(tree != NULL)
    {
        printf("%d", tree->key);
        preorder(tree->left);
        preorder(tree->right);
    }
}

void preorder_rbtree(rbroot * root)
{
    if(root)
        preorder(root->node);
}

//递归实现查找一个结点
static node * search(rbtree x, type key)
{
    if(x == NULL || x->key == key)
        return x;
    if(key < x->key)
        return search(x->left, key);
    else
        return search(x->right, key);
}

int rbtree_search(rbroot * root, type key)
{
    if(root)
        return search(root->node, key) ? 1 : 0;
}

//遍历查找一个结点验证他是否存在
static node * iterate_search(rbtree x, type key)
{
    while((x != NULL) && (x->key != key))
    {
        if(key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return x;
}

int iterate_rbtree_search(rbroot * root, type key)
{
    if(root)
        return iterate_rbtree_search(root->node, key) ? 1 : 0;
}
//查找红黑树中最小的一个结点
static node * minium(rbtree tree)
{
    if(tree == NULL)
        return  NULL;

    while(tree->left != NULL)
        tree = tree->left;
    return tree;
}

int rbtree_minium(rbroot * root, int * value)
{
    node * node;
    if(root)
        node = minium(root->node);
    if(node == NULL)
        return -1;

    *value = node->key;
    return 0;
}

static  node * maximum(rbtree tree)
{
    if(tree == NULL)
        return NULL;
    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}

int rbtree_maximum(rbroot * root, int * value)
{
    node * node;
    if(root)
        node = maximum(root->node);
    if(node == NULL)
        return -1;
    *value = node->key;
    return 0;
}

node * rbtree_successor(node * x)
{
    if(x->right != NULL)
        return minium(x->right);

    node * y = x->parent;
    while( (y != NULL) && (x == y->right)) {
        x = y;
        y = y->parent;
    }
    return y;
}

node * rbtree_predecessor(node * x)
{
    if(x->left != NULL)
        return maximum(x->left);

    node * y = x->parent;
    while((y!=NULL)&&(x==y->left))
    {
        x = y;
        y = y->parent;
    }
    return y;
}


//对x结点进行左旋
static void rbtree_left_rotate(rbroot * root, node * x)
{
    //y指向x的右结点
    node * y = x->right;

    x->right = y->left;
    if(y->left != NULL)
        y->left->parent = x;

    //将x的父亲，设为y的父亲
    y->parent = x->parent;

    if(x->parent == NULL)
        root->node = y;
    else
    {
        if(x->parent->left == x)
            x->parent->left = x;
        else
            x->parent->right = x;
    }

    y->left = x;
    x->parent = y;
}

/**
 * 总结一点，对某个结点的左旋和右旋
 * 就拿右旋来分析
 *
 * 如果对x结点进行右旋转，设y结点是x的左结点
 * 可以理解为x结点将会变成他左结点（y结点）的右孩子
 *
 * 现在要找到x和y之间的结点，那个就是y的右孩子结点
 * 将y的右孩子结点变成x结点的左孩子
 *
 */
//对y结点进行右旋
static void rbtree_right_rotate(rbroot * root, node * x)
{
    //设y结点是x的左结点
    node * y = x->left;

    //y变成x的左子树
    x->left = y->right;
    if(x->left != NULL)
        y = x->left;

    //x的parent变成y的parent
    y->parent = x->parent;
    if(x->parent == NULL)
        root->node = y;
    else if(x->parent->left == x)
        x->parent->left = y;
    else
        x->parent->right = y;

    //x结点将会变成他左结点（y结点）的右孩子
    y->right = x;
    x->parent = y;
}









